【week2】901. Online Stock Span 解题报告

901. Online Stock Span

题目

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.

The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Example 1:

Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation: 
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.

Note:

1. Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
2. There will be at most 10000 calls to StockSpanner.next per test case.
3. There will be at most 150000 calls to StockSpanner.next across all test cases.
4. The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.

解题报告

题意很简单，有一个序列，每次往里面插入 price 时都要往前看有多少个不大于它的数（包括本身），称为 span。

最简单是维护一个 vector，每次查询都往前搜索，本来也想这么做的，但是看评论说有 $O(1)$ 的方法，惊为天人，于是苦思冥想。

这道题明显是需要某种数据结构来配合，再看每次查询的操作，与栈有异曲同工之妙，如果用栈的话，那每次查询必然是将不大于 price 的元素弹出，这样就必须保存状态，则容易想到可以用 pair<int, int> 保存每个 price 的 span，这样如果当前 price 大于等于栈顶的 price ，那也必然大于等于栈顶 price 的 span 包含的 price （可能讲的不太好）。

换个说法，相当于将所有 price 分成一段一段，每一段的最大值留在栈中并记录该段的 price 数目，每次插入时相当于把小段合并成大段再压入栈中。

然而刚开始想到时并不觉得是 $O(1)$ ，实在想不到更好的办法，a了之后再去看那个评论发现和我做法一样。。

Solution

class StockSpanner {
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        int ans = 1;
        while (!stock.empty() && stock.top().first <= price) {
          auto top = stock.top();
          ans += top.second;
          stock.pop();
        }
        stock.push(make_pair(price, ans));
        return ans;
    }
  private:
    stack<pair<int, int>> stock;
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */